\subsection{Definition}
\begin{definition}
	A function \( c \colon V(G) \to \qty{1, \dots, k} \) is a \emph{(proper) \( k \)-colouring} of a graph if \( x \sim y \implies c(x) \neq c(y) \).
	The \emph{chromatic number} of \( G \), denoted \( \chi(G) \), is the minimum \( k \) such that there exists a \( k \)-colouring of \( G \).
\end{definition}
\begin{example}
	A path \( P_n \) has a 2-colouring.
	More generally, a graph is bipartite if and only if it has a 2-colouring.
	An even cycle has chromatic number 2, and an odd cycle has chromatic number 3.
	A tree has chromatic number 2.
	The complete graph on \( n \) vertices has chromatic number \( n \).
\end{example}
\begin{proposition}
	Let \( G \) be a graph.
	Then \( \chi(G) \leq \Delta(G) + 1 \).
\end{proposition}
\begin{proof}
	Let \( x_1, \dots, x_n \) be an ordering of the vertices of \( G \).
	We create a colouring of the vertices by induction.
	Suppose \( x_1, \dots, x_i \) have already been coloured, and we want to colour \( x_{i+1} \).
	Since \( x_{i+1} \) has at most \( \Delta(G) \) neighbours that have already been coloured, but we have \( \Delta(G) + 1 \) available colours, there is a free colour that does not match any previous neighbours.
	Choose the smallest available colour.
	By induction we can colour the entire graph.
\end{proof}
\begin{remark}
	This is sometimes known as a \emph{greedy colouring}.
	The greedy colouring may produce a colouring which is suboptimal for a given graph; consider the path \( P_4 \) on the vertex set \( \qty{1, 2, 3, 4} \) but with the ordering \( 1, 4, 2, 3 \): this gives a 3-colouring.
	The proposition above is sharp: the chromatic number of the complete graph is \( n \), and its maximum degree is \( n - 1 \).
\end{remark}

\subsection{Colouring planar graphs}
\begin{proposition}
	Let \( G \) be planar.
	Then \( \delta(G) \leq 5 \).
\end{proposition}
\begin{proof}
	The average degree of \( G \), given by \( n^{-1} \sum_{v \in V(G)} \deg v \), is exactly \( 2 n^{-1} e(G) \).
	Since \( e(G) \leq 3n - 6 \), the average degree at most \( 6 - \frac{12}{n} < 6 \), so \( \delta(G) \leq 5 \).
\end{proof}
\begin{proposition}[six-colour theorem]
	Let \( G \) be planar.
	Then \( G \) admits a 6-colouring.
\end{proposition}
\begin{proof}
	Apply induction on \( \abs{G} \).
	If \( \abs{G} \leq 6 \), there admits a trivial 6-colouring.
	Let \( G \) be planar, and let \( x \in V(G) \) have degree at most 5.
	By the inductive hypothesis, \( G - x \) admits a 6-colouring.
	Since \( x \) has at most five neighbours, there is a free colour to use for \( x \).
\end{proof}
\begin{theorem}[five-colour theorem]
	Let \( G \) be planar.
	Then \( G \) admits a 5-colouring.
\end{theorem}
\begin{proof}
	We apply induction on \( \abs{G} \).
	Clearly the theorem holds for \( \abs{G} \leq 5 \).
	Suppose \( \abs{G} > 5 \).
	Let \( x \in V(G) \) be a vertex with degree at most five.
	Applying induction, there exists a 5-colouring of \( G - x \).
	If the degree is four or lower, we can use the free colour to colour \( x \), so suppose \( x \) has degree five.
	Let \( N(x) = \qty{x_1, x_2, x_3, x_4, x_5} \) arranged cyclically in the plane, and let the colour of \( x_i \) be \( i \).
	Then without loss of generality, all the \( x_i \) must have different colours, since otherwise, we are done.

	Suppose there exists no path from \( x_1 \) to \( x_3 \) in \( G - x \) only along vertices coloured \( 1 \) and \( 3 \).
	In this case, let \( C \) be the component of \( G \) of vertices coloured \( 1 \) or \( 3 \) that contains \( x_1 \).
	This is the connected component of the subgraph of \( G - x \) induced by the vertices coloured \( 1 \) and \( 3 \) that contains \( x_1 \).
	By assumption, \( x_3 \) is not in this component.
	Now, swap the colours \( 1 \) and \( 3 \) on \( C \); this yields another 5-colouring of \( G - x \).
	We can then extend this 5-colouring to \( x \) by colouring \( x \) with \( 1 \).

	Now, suppose there exists no path from \( x_2 \) to \( x_4 \) in \( G - x \) along vertices coloured \( 2 \) and \( 4 \).
	If so, we are done as above.

	Suppose that there exists an \( x_1 \)--\( x_3 \) path using only colours \( 1 \) and \( 3 \), and an \( x_2 \)--\( x_4 \) path using only colours \( 2 \) and \( 4 \).
	Then since both paths lie in the plane and the vertices are arranged cyclically as above, they must cross.
	The intersection vertex is coloured either \( 1 \) or \( 3 \), and also either \( 2 \) or \( 4 \).
	This is a contradiction.
\end{proof}
\begin{remark}
	Any planar graph admits a 4-colouring; this result is known as the \emph{four-colour theorem}.
	The above method does not work, because when swapping the colours of a component, there is not a free colour to use for the newly added vertex.
	The four-colour theorem was eventually proven using a computer-aided search after reducing the problem to thousands of specific local configurations.
	The four-colour theorem is sharp; \( K_4 \) is planar.
\end{remark}

\subsection{Colouring non-planar graphs}
\begin{proposition}
	Let \( G \) be a connected graph, and \( \delta(G) < \Delta(G) \).
	Then \( \chi(G) \leq \Delta(G) \).
\end{proposition}
\begin{proof}
	Order the vertices in \( G \) into \( x_1, \dots, x_n \) such that \( \deg x_n < \Delta(G) \), and \( x_{n-1} \) is adjacent to \( x_n \), and also \( x_{n-2} \) is adjacent to one of \( x_n \) and \( x_{n-1} \) and so on.
	This is always possible since \( G \) is connected.
	This ordering has the property that all vertices have less than \( \Delta(G) \) edges facing forward.
	So the greedy colouring gives a \( \Delta(G) \)-colouring.
\end{proof}
\begin{theorem}[Brooks]
	Let \( G \) be a connected graph.
	If \( G \) is not an odd cycle or complete graph, \( \chi(G) \leq \Delta(G) \).
\end{theorem}
\begin{remark}
	We have shown above that \( \chi(G) \leq \Delta(G) + 1 \).
	This theorem then says that \( \chi(G) = \Delta(G) + 1 \) if and only if \( G \) is an odd cycle or a complete graph.
\end{remark}
\begin{proof}
	We apply induction on \( \abs{G} \).
	We can check that the theorem holds for \( \abs{G} \leq 3 \).
	Note that we may assume that \( \Delta(G) \geq 3 \); otherwise, the graph is bipartite or an odd cycle.

	We will show first that if \( G \) is 3-connected, the theorem holds.
	We give an ordering of \( V(G) \).
	Let \( x_n \) be a vertex of degree \( \Delta(G) \), and let \( x_1, x_2 \in N(x) \) be non-adjacent vertices.
	This is possible; indeed, suppose we could not find such vertices.
	Then \( \qty{x} \cup N(x) \) is a complete graph, so \( G = K_{\Delta(G) + 1} \) by connectedness, contradicting our assumption.
	Now, consider \( G - \qty{x_1, x_2} \).
	Since \( G \) is 3-connected, \( G - \qty{x_1,x_2} \) is connected.
	We can order the vertices in the same way as above, choosing \( x_{n-1} \sim x_n \) and \( x_{n-2} \) a neighbour of \( x_{n-1} \) or \( x_n \), and so on.
	Then the greedy algorithm produces the required colouring.

	Now, we show that if \( \kappa(G) = 1 \), the theorem holds.
	In this case, we have a separator of size one, so let \( \qty{x} \) be such a separator (we call \( x \) a \emph{cut vertex}).
	Let \( C_1, \dots, C_n \) be the connected components of \( G - x \).
	By induction, we can colour \( C_i \cup \qty{x} \) for each \( i \); they cannot be complete, by counting the number of edges of \( x \) in this graph.
	We can then permute the colours in each such colouring to make \( x \) the same colour.
	Then we can combine each colouring to produce a colouring of the entire graph.

	Finally, we will consider the case when \( \kappa(G) = 2 \).
	Let \( S = \qty{x,y} \) be a separator for \( G \).
	Let \( C_1, \dots, C_k \) be the components of \( G - S \).
	Define the graphs \( G_i = G[C_i \cup S] + xy \) for \( i = 1, \dots, k \).

	Suppose \( \delta(G_i) < \Delta(G) \) for all \( i \).
	In this case, the \( G_i \) can be coloured by induction as they are not complete graphs.
	Note that \( x, y \) get different colours since we have added the edge \( xy \).
	Therefore, we can permute the colours, such that the colouring agrees on \( x,y \) for all \( G_i \).
	These colourings can be combined into a \( \Delta(G) \)-colouring of \( G \).

	Now suppose without loss of generality that \( \delta(G_1) = \Delta(G) \).
	In this case, \( k = 2 \), and
	\[ \abs{N(x) \cap C_1} = \Delta(G) - 1 = \abs{N(x) \cap C_1};\quad \abs{N(x) \cap C_2} = 1 = \abs{N(y) \cap C_2} \]
	Let \( x', y' \) be the neighbours of \( x, y \) in \( C_2 \).
	Now, note that \( \widetilde S = \qty{x,y'} \) is a separator, and now \( \delta(G_i) < \Delta(G) \) for all connected components, and we can use the proof from above.
\end{proof}

\subsection{Chromatic polynomial}
\begin{definition}
	Let \( G \) be a graph.
	The \emph{chromatic polynomial} of \( G \) is \( P_G \colon \mathbb Z_{\geq 0} \to \mathbb Z_{\geq 0} \) where \( P_G(t) \) is the number of \( t \)-colourings of \( G \).
\end{definition}
\begin{remark}
	The minimum \( t \) for which \( P_G(t) > 0 \) the chromatic number.
\end{remark}
\begin{example}
	The chromatic polynomial on the empty graph on \( n \) vertices is given by \( P_G(t) = t^n \).

	The chromatic polynomial on the complete graph on \( n \) vertices is \( P_G(t) = t(t-1)\dots(t-(n-1)) = n! \binom t n \).

	For a path on \( n \) vertices, \( P_G(t) = t(t-1)^{n-1} \).
	For any tree, colouring each leaf, removing it, then colouring the remainder inductively, \( P_G(t) = t(t-1)^{\abs{G} - 1} \).
\end{example}
\begin{definition}
	Let \( G \) be a graph, and \( e = xy \in E(G) \).
	The \emph{contraction} of \( G \) along \( e \), denoted \( G / e \), is the graph with vertices \( V(G) \setminus \qty{x, y} \cup \qty{a} \) for a new variable \( a \), and edges \( E(G[V\setminus\qty{x,y}]) \cup \qty{az \mid x \sim z} \cup \qty{az \mid y \sim z} \).
\end{definition}
\begin{proposition}
	Let \( G \) be a graph and \( e \in E(G) \).
	Then \( P_G(t) = P_{G - e}(t) - P_{G/e}(t) \).
\end{proposition}
\begin{proof}
	Let \( e = xy \).
	A \( t \)-colouring of \( G - e \) where \( x, y \) are assigned different colours corresponds to a \( t \)-colouring of \( G \), by simply adding the edge back.
	A \( t \)-colouring of \( G - e \) where \( x, y \) are assigned the same colour corresponds to a \( t \)-colouring of \( G / e \), by contracting the edge.
\end{proof}
\begin{remark}
	The above proposition is known as a `cut-fuse' relation.
\end{remark}
\begin{proposition}
	Let \( G \) be a graph.
	Then \( P_G(t) \) is indeed a polynomial with degree \( \abs{G} \).
\end{proposition}
\begin{proof}
	We apply induction on \( e(G) \).
	If there are no edges in the graph, the graph is empty, and has chromatic polynomial \( P_G(t) = t^{\abs{G}} \).
	Otherwise, let \( e \in E(G) \).
	By induction, \( P_{G - e}(t) \) is a polynomial of degree \( \abs{G - e} = \abs{G} \), and \( P_{G / e}(t) \) is a polynomial of degree \( \abs{G / e} = \abs{G} - 1 \).
	Hence \( P_G(t) = P_{G - e}(t) - P_{G / e}(t) \) is indeed a polynomial of the required degree.
\end{proof}
\begin{proposition}
	Let \( G \) be a graph with \( n \) vertices and \( m \) edges.
	Then \( P_G(t) = t^n - mt^{n-1} + p(t) \) where \( p \) is a polynomial of degree at most \( n - 2 \).
\end{proposition}
\begin{proof}
	We apply induction on \( e(G) \).
	If there are no edges, we have the empty graph, which has the required form.
	Otherwise, let \( e \in E(G) \).
	Then
	\[ P_G(t) = P_{G - e}(t) - P_{G/e}(t) = \qty(t^n - (m - 1)t^{n-1} + \dots) + \qty(t^{n-1} + \dots) = t^n - mt^{n-1} + \dots \]
	as required.
\end{proof}
\begin{remark}
	Other coefficients of the chromatic polynomial contain other information about the graph.
	For example, the \( t^{n-2} \) coefficient is exactly \( \binom{e(G)}{2} - \text{number of triangles in } G \).

	If \( G \) is planar, \( P_G\qty(2+\frac{1+\sqrt{5}}{2}) \neq 0 \).

	A result due to June Huh is that the coefficients \( c_0, \dots, c_n \) of \( P_G \) are \emph{log-concave}, so \( c_i^2 > c_{i-1}c_{i+1} \).
\end{remark}

\subsection{Edge colouring}
\begin{definition}
	Let \( G \) be a graph.
	A \emph{\( k \)-edge colouring} is a function \( c \colon E(G) \to \qty{1, \dots, k} \) such that if \( c(e) \neq c(f) \) if \( e, f \) share an endpoint.
	The \emph{edge chromatic number}, or the \emph{chromatic index}, denoted \( \chi'(G) \), is the minimum \( k \) such that there exists a \( k \)-edge colouring.
\end{definition}
\begin{remark}
	An edge colouring of \( G \) corresponds exactly to a vertex colouring of the line graph of \( G \).
	In particular, \( \chi'(G) = \chi(L(G)) \).
	Note that not every graph can be realised as the line graph of some other graph.
\end{remark}
\begin{example}
	The edge chromatic number of an even cycle is 2.
	The edge chromatic number of an odd cycle is 3.
	This is because a cycle is its own line graph.
\end{example}
\begin{example}
	We have \( \Delta(G) \leq \chi'(G) \).
	If \( x \in V(G) \) has degree \( \Delta(G) \), all edges indicent to \( x \) must be given different colours.
	We may have \( \Delta(G) < \chi'(G) \) for some graphs, such as \( C_3 \).
	The edge chromatic number of the Petersen graph is 4, but it is 3-regular.

	We can show that \( \chi'(G) \leq 2\Delta(G) - 1 \) by the greedy colouring, considering how many vertices each edge can be connected to.
	\( \chi' \) and \( \chi \) can be very different, for instance, consider \( \chi(K_{t,1}) = 2 \) but \( \chi'(K_{t,1}) = t \).
\end{example}
Given an edge colouring \( c \colon E(G) \to \qty{1, \dots, k} \), we define the \emph{colour classes} as equivalence classes of colours: \( C_i = \qty{e \in E(G) \mid c(e) = i} \).
Note that \( (V(G), C_i \cup C_j) \) is the union of disjoint paths, even cycles, and isolated vertices.
We say that the components of this graph are \emph{\( \qty{i,j} \)-components}.
\begin{theorem}[Vizing]
	Let \( G \) be a graph.
	Then \( \chi'(G) = \Delta(G) \) or \( \chi'(G) = \Delta(G) + 1 \).
\end{theorem}
\begin{proof}
	We prove this by induction on \( \abs{E(G)} \).
	It suffices to show there is a \( \Delta(G) + 1 \) colouring of any graph.
	If there are no edges, the graph can be \( 0 \)-coloured, so \( \chi'(G) = \Delta(G) = 0 \) and so there is clearly a \( 1 \)-colouring.
	For the inductive step, let \( G \) be a graph with \( e(G) > 0 \), and \( xv \in E(G) \).
	Apply induction to \( G - xv \) to obtain a \( \Delta(G) + 1 \) edge colouring.

	Let \( y \in V(G) \) and \( c \in \qty{1, \dots, \Delta(G) + 1} \).
	We say \( c \) is \emph{missing} at \( y \) if no edge incident to \( y \) are coloured \( c \).
	Note that there is a colour missing at every vertex since we have \( \Delta(G) + 1 \) different colours available.

	Let \( c_0 \) be a colour missing at \( x \).
	We define a sequence of vertices \( v_1, \dots, v_k \in N(x) \) and corresponding colours \( c_1, \dots, c_k \) such that \( c_i \) is missing at \( v_i \).
	First, we set \( v_1 = v \) and let \( c_1 \) be any colour missing at \( v \).
	Then if \( v_i \) and \( c_i \) are defined, define \( v_{i+1} \) such that \( c(xv_{i+1}) = c_i \), and define \( c_{i+1} \) to be any colour missing at \( v_{i+1} \).
	This induction continues until either we find a colour missing at \( x \) or we repeat a colour.

	Suppose \( v_1, \dots, v_k \) are defined and \( c_k \) is missing at \( x \).
	Then we can recolour \( xv_k \) with \( c_k \).
	Now \( c_{k-1} \) is missing at \( x \), so inductively, recolour \( xv_i \) with \( c_i \).
	In particular, \( c_1 \) is missing at \( x \), so we can colour \( xv_1 \) with \( c_1 \).

	In the other case, suppose \( c_k = c_i \) for \( i < k \).
	Note that we may assume \( i = 1 \): uncolour \( xv_{i-1} \) and recolour \( xv_j \) with \( c_j \) for all \( j < i \) as above.
	So \( c_k = c_1 \).
	If \( v_1 \) is not in the same \( \qty{c_0, c_1} \) component as \( x \), we can swap the colours on the \( \qty{c_0, c_1} \) component containing \( v_1 \).
	Then \( c_0 \) is missing at \( v_1 \), and the colours of \( xv_2, \dots, xv_k \) are unchanged.
	So we can colour \( xv_1 \) with \( c_0 \).

	Now suppose \( x, v_1 \) are in the same \( \qty{c_0, c_1} \) component.
	If \( v_k \) is not in the same \( \qty{c_0, c_1} \) component as \( x \), we can similarly swap the colours on the \( \qty{c_0, c_1} \) component containing \( v_k \).
	So \( c_0 \) is missing at \( v_k \) and \( x \), and so we can recolour \( xv_k \) to \( c_0 \), and inductively \( xv_i \) with \( c_i \).

	Now finally suppose \( x, v_1, v_k \) are all in the same \( \qty{c_0, c_1} \) component.
	So one of \( c_0, c_1 \) are missing at each of \( x, v_1, v_k \).
	Since all \( \qty{c_0, c_1} \)-components of the graph are disjoint paths, even cycles, or isolated vertices.
	So \( x, v_1, v_k \) are each endpoints of a path.
	But since paths only have two endpoints, this is a contradiction.
\end{proof}

\subsection{Graphs on surfaces}
We have seen that a planar graph has chromatic number \( \chi(G) \leq 5 \).
Drawing graphs on other surfaces give different possible chromatic numbers.
For instance, the complete graph on seven vertices \( K_7 \) can be drawn on a torus with no edge crossings.
\ctikzfig{k7_torus}
Recall from IB Geometry that for any \( g \in \mathbb N \), there is a \emph{compact orientable surface of genus \( g \)} which is homeomorphic to a sphere with \( g \) `handles' attached.
The 2-sphere \( S^2 \) is a compact orientable surface of genus 0.
The torus \( T^2 \) is a compact orientable surface of genus 1.

We have already seen that for a connected planar graph \( G \) with \( f \) faces, we have \( \abs{G} - e(G) + f = 2 \).
For a disconnected planar graph, we can add edges to make \( G \) into a connected graph.
Hence, any planar graph with \( f \) faces satisfies \( \abs{G} - e(G) + f \leq 2 \).
In general, on the compact orientable surface of genus \( g \), \( \abs{G} - e(G) + f \leq E \), where \( E = 2 - 2g \) is the Euler characteristic of the surface.
Due to results from IB Geometry, the equality holds for connected graphs, and then for any other graph, we can add edges to make it connected.

In particular, if \( e(G) \geq 3 \), then \( 3f \leq 2e(G) \) as usual.
Therefore, \( \abs{G} - e(G) + \frac{2e(G)}{3} \geq E \), and so \( e(G) \leq 3(\abs{G} - E) \).
\begin{theorem}[Heawood]
	Let \( G \) be a graph drawn on a surface of Euler characteristic \( E \leq 0 \).
	Then
	\[ \chi(G) \leq H(E) = \floor*{\frac{7+\sqrt{49-24E}}{2}} \]
\end{theorem}
\begin{remark}
	Note that \( H(2) = 4 \), which would prove the four-colour theorem if not for the requirement that \( E \leq 0 \).
\end{remark}
\begin{proof}
	Let \( G \) be a graph drawn on a given surface with Euler characteristic \( E \).
	Suppose its chromatic number is \( \chi(G) = k \).
	Without loss of generality, we can choose a minimal such graph \( G \) with \( \chi(G) = k \).

	Each vertex has degree at least \( k - 1 \).
	Indeed, suppose there was a vertex of degree less than \( k - 1 \).
	Then we could remove this vertex and all associated edges, and we would obtain a strictly smaller graph with chromatic number exactly \( k \), contradicting minimality.
	Further, we have \( \abs{G} \geq k \), otherwise we could colour the graph with only \( \abs{G} \) colours contradicting the definition of the chromatic number.

	Since \( e(G) \leq 3(\abs{G} - E) \), the sum of the degrees of the vertices is \( 2e(G) \leq 6(\abs{G} - E) \).
	Hence, \( \delta(G) \leq \frac{1}{\abs{G}} 6(\abs{G} - E) = 6 - 6\frac{E}{\abs{G}} \).
	In particular,
	\[ k - 1 \leq \delta(G) \leq 6 - 6\frac{E}{\abs{G}} \leq 6 - 6\frac{E}{k} \]
	Note that this step requires the fact that \( E \leq 0 \).
	This gives the quadratic equation \( k^2 - 7k + 6E \leq 0 \).
	Then,
	\[ \qty(k - \frac{7}{2})^2 - \frac{49}{4} + 6E \leq 0 \implies k \leq \frac{7 + \sqrt{49 - 24E}}{2} \]
\end{proof}
\begin{remark}
	The inequality is sharp, since the complete graph \( K_{H(E)} \) can be drawn on a surface of characteristic \( E \).
	An example of this is drawing \( K_7 \) on the torus, as demonstrated above.
	However, this is a very difficult result to prove.
\end{remark}
